package com.leetcode.回溯;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

//子集
public class lc_48 {
    public static void main(String[] args) {

    }

    //给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
    //解集 不能 包含重复的子集。你可以按 任意顺序 返回解集

    /**
     * 1.画出递归树，找到状态变量(回溯函数的参数)：
     * - nums: 输入数组，固定不变
     * - res: 结果集，存储所有子集
     * - path: 当前递归路径上的选择
     * - start: 控制选择列表的起始位置，避免重复选择
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>(); // 存储最终结果的集合
        Deque<Integer> path = new ArrayDeque<>();    // 存储当前路径的元素
        backTrack(nums, res, path, 0);               // 从索引0开始回溯
        return res;
    }

    /**
     * 回溯函数
     * @param nums 输入数组
     * @param res 结果集
     * @param path 当前路径的元素
     * @param start 选择列表的起始位置
     */
    void backTrack(int[] nums, List<List<Integer>> res, Deque<Integer> path, int start) {
        // 2.确立结束条件：
        // 当start >= nums.length时，循环自然结束，无需额外终止条件

        // 收获结果：每个节点状态都是一个子集（包括空集）
        res.add(new ArrayList<>(path)); // 必须拷贝path，避免后续修改影响结果

        // 3.找准选择列表：
        // 从start开始到数组末尾的所有元素（避免重复组合）
        for (int i = start; i < nums.length; i++) {
            // 4.判断是否需要剪枝：
            // 本题所有选择都是有效的，无需剪枝

            // 5.作出选择：
            path.addLast(nums[i]); // 将当前元素加入路径

            // 递归进入下一层：
            // 注意：这里传入i+1而非start+1，确保后续选择从i+1开始，避免重复
            backTrack(nums, res, path, i + 1);

            // 6.撤销选择：
            // 回溯到上一层，移除最后一次的选择
            path.removeLast();
        }
    }
}
